Referring to both FIG. 1 and FIG. 2. FIG. 1 shows a Huffman table 10 at an encoding end. FIG. 2 shows a complete reconstructed Huffman table 20 at a decoding end. To assure data consistency, the encoding end and the decoding end must use the same Huffman table, so that the encoding end generates a symbol array Sym[ ] and a number-of-Huffman-code array NC[ ] according to the Huffman table 10. The symbol array Sym[ ] comprises all symbols in the Huffman table 10, wherein the symbols are arranged in an ascending order according to the code values of the corresponding Huffman code of the symbols. For example, the code values of the Huffman codes in the Huffman table 10 are arranged in an ascending order as 0, 2, 3, 4, 5, 6, 14, 30, 62, 126, 254, 510 (that is, the binary digits: 00, 010, 011, 100, 101, 110, 1110, 11110, 111110, 1111110, 11111110, 111111110), so the symbols in the symbol array are also arranged according to the sequence of the code values of the Huffman codes, and the corresponding symbol array is Sym[ ]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. The number-of-Huffman-code array NC[ ] records the number of Huffman codes corresponding to each code length. The corresponding number-of-Huffman-code array of the Huffman table 10 is expressed as: NC[ ]={0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0}. It is indicated in the Huffman table 10 there is no 1-bit Huffman code, one 2-bit Huffman code, five 3-bit Huffman codes, one Huffman code for each of the 4˜9-bit Huffman codes, and zero Huffman code for each of the 10˜16-bit Huffman codes. The encoding end stores the symbol array Sym[ ] and the number-of-Huffman-code array NC[ ] in a file header, and the decoding end reconstructs the Huffman table 20 according to the symbol array Sym[ ] and the number-of-Huffman-code array NC[ ] in the file header and generates a look-up table according to the Huffman table 20.
It is noted that the Huffman code indexes of FIG. 2 are exactly identical to the symbol values, which are arranged in a continual order. However, this is only an exceptional case, which does not occur to all Huffman tables.
Referring to both FIG. 2 and FIG. 3. FIG. 3 shows a conventional look-up table for leading 1's search algorithm. The lookup index m′ for the look-up table 30 is equal to the number of leading 1's of the Huffman code in the Huffman table 20, and the Huffman code index Lookup[m′] for the look-up table 30 is the Huffman code index n′ for the Huffman table 20, wherein n′=Lookup[m′]. Thus, the corresponding lookup index m′ for the look-up table 30 can be obtained according to the number of leading 1's in the to-be-decoded bit stream. After that, the Huffman code index n′ for the Huffman table 20 can be obtained according to the corresponding Huffman code index Lookup[m′] for the lookup index m′. Lastly, the corresponding symbol is obtained by searching the Huffman codes and bit lengths in the Huffman table 20 according to Huffman code index n′.
To make the conventional leading 1's search decoding method easier to understand, let the bit stream be exemplified by 0111011 below. Firstly, the number of leading 1's in the bit stream 0111011 is equal to 0. That is, the lookup index m′ for the look-up table 30 is equal to 0. Next, as the lookup index m′ is equal to 0, the Huffman code index Lookup[m′] for the look-up table 30 equals Lookup[0]=0. Then, as the Huffman code index Lookup[0] for the look-up table 30 is equal to 0, the Huffman code index n′ for the Huffman table 20 is equal to 0, and the Huffman table 20 is searched from the Huffman code index n′ being equal to 0.
The corresponding Huffman code of the Huffman code index n′ being equal to 0 is 00 and the bit length is 2, so the first 2 most significant bits (MSB) of the bit stream 0111011, which are 01, are compared with the Huffman code 00. As the bits 01 do not match with 00, the method continues to search the Huffman table 20 downward.
The next Huffman code index n′ is equal to 1. As the corresponding Huffman code of the Huffman code index n′ being equal to 1 is 010 and the bit length is 3, the first 3 most significant bits of the bit stream 0111011, which are 011, are compared with the Huffman code 010. As the bits 011 do not match with 010, the method continues to search the Huffman table 20 downward.
The next Huffman code index n′ is equal to 2. As the corresponding Huffman code of the Huffman code index n′ being equal to 2 is 011 and the bit length is 3, the first 3 most significant bits of the bit stream 0111011, which are 011, are compared with the Huffman code 011. As the bits 011 match with 011, the method stops searching the Huffman table 20. When the Huffman code index n′ is equal to 2, Sym[n′]=Sym[2]=2, the decoded symbol is 2 and the bit length is 3. Lastly, the 3 most significant bits are removed from the bit stream 0111011 to generate the new bit stream 1011.
To make the conventional leading 1's search decoding method easier to understand, let the bit stream be exemplified as 0010 below. Firstly, the number of leading 1's in the bit stream 0010 is equal to 0. That is, the lookup index m′ for the look-up table 30 is equal to 0. Next, as the lookup index m′ is equal to 0, the Huffman code index Lookup[m′] for the look-up table 30 equals Lookup[0]=0. Then, as the Huffman code index Lookup[0] for the look-up table 30 equals 0, the Huffman code index n′ for the Huffman table 20 is equal to 0, and the Huffman table 20 is searched from the Huffman code index n′ being equal to 0.
The corresponding Huffman code of the Huffman code index n′ being equal to 0 is 00 and the bit length is 2, so the first 2 most significant bits of the bit stream 0010, which are 00, are compared with the Huffman code 00. As the bits 00 match with 00, the method stops searching the Huffman table 20. When the Huffman code index n′ is equal to 0, Sym[n′]=Sym[0]=0, the decoded symbol is 0 and the bit length is 2. Lastly, the 2 most significant bits are removed from the bit stream 0010 to obtain the new bit stream 10.
Thus, when the conventional leading 1's search method is used for searching the bit stream 0111011 and the bit stream 0010, at least 4 iterations of search are required to obtain the corresponding symbols 2 and 0.
Referring to FIG. 4, a look-up table for conventional one-bit binary search algorithm is shown. The look-up table 40 comprises a column Index and a column Content. The column Index comprises a node Node and a bit Bit, and the column Content comprises a value NodeSE and a flag Flag. Different nodes and bits respectively correspond to different values NodeSE and flags Flag. The node at the beginning of search must be 0 and the Bit is input one by one from the bit stream.
When the flag Flag equals 1, this implies that the binary search already finishes, and the value NodeSE is the corresponding symbol of the bit stream. To the contrary, when the flag Flag equals 0, this implies that the binary search has not yet finished, and the value NodeSE denotes the next node Node. Another binary search is performed according to the next node Node and the next bit Bit.
The symbol corresponding to the received bit stream can be located by searching the look-up table 40. To make the conventional one-bit binary search decoding method easier to understand, let the bit stream be exemplified as 0111011 below.
Firstly, the node Node is equal to “0”, and the first bit in the bit stream is equal to “0”, and the flag Flag and the value NodeSE which correspond to the node Node “0” and the bit Bit “0” are located by performing a first binary search and the flag Flag is “0”, and the value NodeSE is “1”. When the flag Flag equals “0”, this implies that the search has not yet finished, and when the value NodeSE equals “1”, this implies that the next node Node is “1”.
Next, the node Node is “1”, and the second bit in the bit stream is “1”, and the flag Flag and the value NodeSE which correspond to the node Node “1” and the bit Bit “1” are located by performing a second binary search and the flag Flag is “0”, and the value NodeSE is “3”. When the flag Flag equals “0”, this implies that the search has not yet finished; and when the value NodeSE equals “3”, this implies that the next node Node is “3”.
Then, the node Node is equal to “3”, the third bit in the bit stream is equal to “1”, and the flag Flag and the value NodeSE which correspond to the node Node “3” and the bit Bit “1” are located by performing a third binary search and the flag Flag is “1”, and the value NodeSE is “2”. When the flag Flag equals “1”, this implies that the search has finished; and when the value NodeSE equals “2”, this implies that the decoded symbol is “2”.
To make the conventional one-bit binary search decoding method easier to understand, the bit stream 0010 is exemplified below.
Firstly, the node Node is equal to “0”, and the first bit in the bit stream is equal to “0”, and the flag Flag and the value NodeSE which correspond to the node Node “0” and the bit Bit “0” are located by performing a first binary search and the flag Flag is “0”, and the value NodeSE is “1”. When the flag Flag equals “0”, this implies that the search has not yet finished; and when the value NodeSE equals “1”, this implies that the next node Node is “1”.
Next, the node Node is equal to “1”, the second bit in the bit stream is equal to “0”, and the flag Flag and the value NodeSE which correspond to the node Node “1” and the bit Bit “0” are located by performing a second binary search and the flag Flag is “1”, and the value NodeSE is “0”. When the flag Flag equals “1”, this implies that the search has finished; and when the value NodeSE equals “0”, this implies that the decoded symbol equals “0”.
Thus, when the bit stream 0111011 and the bit stream 0010 are searched by the conventional one-bit binary search method, at least 5 iterations of search are required for obtaining the corresponding symbol 2 and symbol 0.